This invention relates generally to the field of image display and reproduction, and specifically to the display and reproduction of digitally-stored monochrome and color images using irregularly placed curving structures, where such display and reproduction is accomplished using a monitor, a printer, a plotter, or a typesetter. The digital images may consist of elements that have been scanned, manually digitized graphics, or computer generated graphics or text.
Color and monochrome reproduction devices such as monitors, printers, and typesetters display, print, or typeset images using a grid of pixels. In such systems each pixel in the grid of pixels is set to a pixel intensity value within a range of possible intensity values. The permitted range of possible values is determined by the printing or display process adopted.
In many systems the range of pixel intensity values present in the digital image to be reproduced is greater than the range of pixel intensity values permitted by the display, printing or typesetting process. For example, the digital image might contain color values represented by 8 bits (256 possible levels of intensity) per pixel per color channel, while the printing device may be capable at any given point on the paper of printing ink, or leaving the paper without ink, resulting in 1-bit (two possible levels of intensity) per pixel per color channel. In these cases images must be reproduced by setting the intensity values of pixels such that, over a suitably chosen area, the average of the pixel intensity values of the displayed, printed, or typeset image is approximately equal to the average image pixel intensity over the same area of the digital image. This process is known as "halftoning."
Many methods exist for converting from many bits per pixel to few bits per pixel. One such method is known as "threshold array" halftoning. Using this method a threshold array is defined that contains data representing a halftone screen element, or a spot function, that is repeated periodically across the image to be reproduced. The spot function contains data with the same range as that of the digital image data to be halftoned and at the same resolution as the output device. As the value of each output pixel is calculated the corresponding pixel in the threshold array is selected, along with the corresponding digital image input pixel. For each output pixel the value of the then current input pixel and the threshold array pixel are compared. If the input data pixel value is higher than the threshold array pixel the corresponding output pixel is set to its "on" state. If the input data value is less than or equal to the threshold array pixel the corresponding output pixel is set to its "off" state. The values of the pixels in the threshold array, or the "spot function" determines the shape of the resulting half tone dot for any given shade of tone or color of the input data.
The values of the pixels in the threshold array also indicate the order in which the corresponding device pixels are to be illuminated as the gray, or color, intensity is increased from zero to full intensity. This is referred to as the order of illumination of pixels. If this processing is employed in an environment were an output pixel may have more than two levels, known methods may be used to apply the halftone cell description to a multilevel output device.
Most halftone screening systems using threshold arrays use spot functions that create highly clustered halftone dots having compact and regular shapes such as squares, ellipses, or circles on grids of fixed spatial frequency, or line screen ruling that typically ranges from about 65 lines per inch to about 200 lines per inch. This regular and fixed pattern of dots causes interference, or moire, patterns under a wide variety of conditions. The fixed and regular screen ruling and highly clustered dot structure also limits the visual sharpness of pictures reproduced using this method.
Threshold array spot functions can also be created that are not clustered. A non clustered but regular halftone dot shape is produced by Bayer dither that can easily be expressed in terms of a spot function or a threshold array. Bayer dither produces results that have very fine structures, and thus cannot be printed using some systems. Bayer dither also maintains a very regular pattern that caused severer interference, or moire, patterns under some conditions.
It is also possible to produce non clustered structures that do not form a regular, periodic, pattern by defining the spot function as successive samples of a random and uncorrelated variable. Though "random" screening is free from moire effects due to the fact that no regular pattern exists, and produces images with greater apparent sharpness than does conventional clustered dot screening, random screening suffers from two major drawbacks. Because it is random and uncorrelated, clusters of random size and position form. These clusters may make images look "noisy" or "grainy." Because many of the structures using random screening are uncontrollably small and since, at any given shade of tone or color, structures of many different sizes are present due to the random clustering of output pixels, the resulting random halftone patterns are difficult to print and some printing processes that use them are inherently unstable.
It is possible to shape the "spectrum" of a random screen structure. This still results in random patterns, but introduces some correlation which reduces the appearance of graininess to some degree.
Some other known techniques for digital halftoning operate by selecting a suitable halftone pixel value, estimating the error between this value and the digital image input pixel intensity value, and compensating for this error when selecting the halftone pixel value for neighboring pixels. These techniques are known collectively as error diffusion halftoning. Error diffusion halftoning has the disadvantage of producing distracting artifacts in the form of long and narrow connected structures, and is computationally intensive, thus causing very long data processing times.
The halftones produced using any of the known "non-clustered" techniques cannot be accurately imaged using some standard printing techniques as in some cases individual pixels are produced that are smaller than the minimum size that can be reproduced. Techniques aimed at improving printability by simple pixel replication may result in a reduction of the apparent resolution of the image, or an increase in the visual noise or graininess.
Color images may be reproduced using multiple halftone screens. For example, when using cyan, magenta, yellow and black printing inks, images are processed to produce color separations, or color channels, and each color separation is reproduced using a method similar to that for monochrome images. These, when overlaid, form complex patterns of color mixtures on a very small scale. When viewed at normal viewing distances the limited resolving power of the observer's eye merges these patterns together to cause the sensation of nearly homogeneous areas of color. The periodic patterns used with conventional clustered dot screening disturb the homogeneous sensation adding to the "roughness" of color tone. Many of the "random" screening methods produce images that appear "grainy" or "noisy," and so do not have a homogeneous, or smooth appearance.
It would be desirable to be able to produce halftone patterns that have combinations of both random and ordered structures that have properties of increased perception of smoothness, homogeneity of color, freedom from interference or moire patterns, and that have controllable cluster sizes to establish stable and controllable printing conditions.